Many decoders (and encoders) receive (and encoders provide) encoded data for blocks of an image. Typically, the image is divided into blocks and each of the blocks is encoded in some manner, such as using a discrete cosine transform (DCT), and provided to the decoder. A block may denote a rectangular region in an image and consist of pixels, for example a 16×16 block is a region 16× pixels in width and 16× pixels in height. The decoder receives the encoded blocks and decodes each of the blocks in some manner, such as using an inverse discrete cosine transform.
Video coding standards, such as MPEG-4 part 10 (H.264), compress video data for transmission over a channel with limited frequency bandwidth and/or limited storage capacity. These video coding standards include multiple coding stages such as intra prediction, transform from spatial domain to frequency domain, quantization, entropy coding, motion estimation, and motion compensation, in order to more effectively encode and decode frames.
The Joint Collaborative Team on Video Coding (JCT-VC) of the International Telecommunication Union Telecommunication Standardization Sector (ITU-T) Study Group 16 (SG16) Working Party 3 (WP3) and International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) Joint Technical Committee 1/Subcommittee 29/Working Group 11 (JTC1/SC29/WG11) has launched a standardization effort for a video coding standard called the High Efficiency Video Coding standard (HEVC). Similar to some prior video coding standards, HEVC is block-based coding. An example of a known HEVC encoder is shown in FIG. 1. HEVC decoders are also known.
In HEVC, Context-Adaptive Binary Arithmetic Coding (CABAC) is used to compress Transformed and Quantized Coefficients (TQCs) without loss. The TQCs are determined at the encoder by processing image blocks with a forward transform to generate transform coefficients that are then quantized using an operation that maps multiple transform coefficient values to TQCs values. The TQCs values are then communicated to the decoder as Coefficient Level values, or level values, and the level value for each coefficient is then mapped to a transform coefficient value that is similar, but not necessarily identical to, the transform coefficient value computed at the encoder. CABAC based encoding and/or decoding technique is generally context adaptive which refers to (i) adaptively coding symbols based on the values of previous symbols encoded and/or decoded in the past, and (ii) context, which identifies the set of symbols encoded and/or decoded in the past used for adaptation. The past symbols may be located in spatial and/or temporal adjacent blocks. In many cases, the context is based upon symbol values of neighboring blocks.
As mentioned above, CABAC may be used to compress TQCs without loss. By way of background, TQCs may be from different block sizes according to transform sizes (e.g., 4×4, 8×8, 16×16, 32×32, 16×32). Two-dimensional (2D) TQCs may be converted into a one-dimensional (1D) array before entropy coding. In an example, 2D arrayed TQCs in a 4×4 block may be arranged as illustrated in Table (1).
TABLE (1)401032−1. . .−30. . .. . .0. . .. . .. . .
When converting the 2D TQCs into a 1D array, the block may be scanned in a diagonal zig-zag fashion. Continuing with the example, the 2D arrayed TQCs illustrated in Table (1) may be converted into 1D arrayed TQCs [4, 0, 3, −3, 2, 1, 0, −1, 0, . . . ] by scanning the first row and first column, first row and second column, second row and first column, third row and first column, second row and second column, first row and third column, first row and fourth column, second row and third column, third row and second column, fourth row and first column and so on.
The 1D array of TQCs is represented by a sequence of Syntax Elements (SEs) in CABAC. An example of the sequence of SEs for the example 1D array of TQCs is shown in FIG. 2. The SEs represent the following parameters: Last position X/Y, Significance Map, and the attributes Greater than 1, Greater than 2, Sign Information, and Absolute −3. The last position X/Y represents the position (X/Y) of the last non-zero coefficient in the corresponding block. Significance map represents the significance of each coefficient. Greater than 1 indicates whether the coefficient amplitude is larger than one for each non-zero coefficient (i.e. with significant flag as 1). Greater than 2 indicates whether the coefficient amplitude is larger than two for each coefficient with amplitude larger than one (i.e. with greater than 1 flag as 1).
In CABAC in HEVC, the representative SEs are coded. FIG. 3 shows the CABAC framework used for coding SEs. The CABAC coding technique includes coding symbols using stages. In the first stage, the CABAC uses a “binarizer” to map input symbols to a string of binary symbols, or “bins”. The input symbol may be a non-binary valued symbol that is binarized or otherwise converted into a string of binary (1 or 0) symbols prior to being coded into bits. The bins can be coded into bits using either a “bypass encoding engine” or a “regular encoding engine”.
For the regular encoding engine in CABAC, in the second stage a probability model is selected. The probability model is used to arithmetic encode one or more bins of the binarized input symbols. This model may be selected from a list of available probability models depending on the context, which is a function of recently encoded symbols. The probability model stores the probability of a bin being “1” or “0”. In the third stage, an arithmetic encoder encodes each bin according to the selected probability model. There are two sub-ranges for each bin, corresponding to a “0” and a “1”. The fourth stage involves updating the probability model. The selected probability model is updated based on the actual encoded bin value (e.g., if the bin value was a “1”, the frequency count of the “1”s is increased). The decoding technique for CABAC decoding reverses the process.
For the bypass encoding engine in CABAC, the second stage involves conversion of bins to bits omitting the computationally expensive context estimation and probability update stages. The bypass encoding engine assumes a fixed probability distribution for the input bins. The decoding technique for CABAC decoding reverses the process.
The CABAC encodes the symbols conceptually using two steps. In the first step, the CABAC performs a binarization of the input symbols to bins. In the second step, the CABAC performs a conversion of the bins to bits using either the bypass encoding engine or the regular encoding engine. The resulting encoded bit values are provided in the bitstream to a decoder.
The CABAC decodes the symbols conceptually using two steps. In the first step, the CABAC uses either the bypass decoding engine or the regular decoding engine to convert the input bits to bin values. In the second step, the CABAC performs de-binarization to recover the transmitted symbol value for the bin values. The recovered symbol may be non-binary in nature. The recovered symbol value is used in remaining aspects of the decoder.
As previously described, the encoding and/or decoding process of the CABAC includes at least two different modes of operation. In a first mode, the probability model is updated based upon the actual coded bin value, generally referred to as a “regular coding mode”. The regular coding mode requires several sequential serial operations together with its associated computational complexity and significant time to complete. In a second mode, the probability model is not updated based upon the actual coded bin value, generally referred to as a “bypass coding mode”. In the second mode, there is no probability model (other than perhaps a fixed probability) for decoding the bins, and accordingly there is no need to update the probability model.
When utilizing CABAC coding in HEVC, throughput performance can differ depending on different factors such as but not limited to: total number of bins/pixels, number of bypass bins/pixels, and number of regular (or context) coded bins/pixels. Generally speaking, throughput for the case of high bit-rate encoding (low Quantization Parameter (QP) value) is significantly less than throughput in other cases. Therefore, throughput in high bit-rate cases may consume a significant amount of processing resources and/or may take a significant amount of time to encode/decode. The disclosure that follows solves this and other problems.
It is also known that CABAC can be used in a lossless coding mode to compress a residual sample. In one example, a residual sample is a value corresponding to a specific location in an image. Typically, a residual sample corresponds to the difference between a value corresponding to a specific location in an image and a prediction value corresponding to the same, specific location in an image. Alternatively, a residual sample is a value corresponding to a specific location in an image that has not been processed with a transformation operation, or a transformation operation that is not typically used to create TQCs. A residual sample can be from different block sizes according to its sample size (4×4, 8×8, 16×16, 32×32, 16×32, etc.) A 2D residual sample block is first converted into a 1D array before entropy coding, similar to TQC encoding. In an example, 2D arrayed residual sample in a 4×4 block may be arranged as illustrated in Table (2).
TABLE (2)401032−1. . .−30. . .. . .0. . .. . .. . .
When converting the 2D residual sample into a 1D array, the block may be scanned in a diagonal zig-zag fashion. Continuing with the example, the 2D arrayed residual sample illustrated in Table (2) may be converted into 1D arrayed residual sample [4, 0, 3, −3, 2, 1, 0, −1, 0, . . . ] by scanning the first row and first column, first row and second column, second row and first column, third row and first column, second row and second column, first row and third column, first row and fourth column, second row and third column, third row and second column, fourth row and first column and so on.
The 1D array of the residual sample is represented by a sequence of Syntax Elements (SEs) in CABAC. An example of a sequence of SEs for the example 1D array of the residual sample is shown in FIG. 11. The SEs represent the following parameters: Last position X/Y, Significance Map, and the attributes Greater than 1, Greater than 2, Sign Information, and Absolute −3.
In the lossless coding mode of CABAC in HEVC, the representative SEs are coded. The CABAC framework of FIG. 3 may be used for coding the SEs. The CABAC coding technique includes coding symbols using stages. In the first stage, the CABAC uses a “binarizer” to map input symbols to a string of binary symbols, or “bins”. The input symbol may be a non-binary valued symbol that is binarized or otherwise converted into a string of binary (1 or 0) symbols prior to being coded into bits. The bins can be coded into bits using the previously described “regular encoding engine”.
For the regular encoding engine in the lossless coding mode of CABAC, in the second stage a probability model (also known as a “context model” in the lossless encoding mode of CABAC) is selected. The model is used to arithmetic encode one or more bins of the binarized input symbols. This model may be selected from a list of available models depending on the context, which is a function of recently encoded symbols. The model stores the probability of a bin being “1” or “0”. In the third stage, an arithmetic encoder encodes each bin according to the selected model. There are two sub-ranges for each bin, corresponding to a “0” and a “1”. The fourth stage involves updating the model. The selected model is updated based on the actual encoded bin value (e.g., if the bin value was a “1”, the frequency count of the “1” s is increased). The decoding technique for CABAC decoding reverses the process.
The number of models used as described in the previous paragraph may be 184. Specifically: 36 models used for Last position X/Y (18 models for Last_pos_X, 18 models for Last_pos_Y); 48 models used for Significance Map (4×4 block: 9 luma, 6 chroma; 8×8 block: 11 luma, 11 chroma; 16×16 or 32×32 block: 7 luma, 4 chroma); and 100 models used for the attributes Greater than 1, Greater than 2, Sign Information, and Absolute −3 (Greater_than_1 flag of luma: 30; Greater_than_1 flag of chroma 20, Greater_than_2 flag of luma: 30; and Greater_than_2 flag of chroma 20).
When utilizing CABAC encoding in HEVC in the lossless coding mode, encoding/decoding is computationally complex. One reason for the computation complexity is the use of 184 models, as explained above. Due to this computation complexity, encoding/decoding may consume a significant amount of processing resources and/or may take a significant amount of time to complete. The disclosure that follows solves this and other problems.